package com.ljy.my_study.leetcode.不同的二叉搜索树;

/**
 * @author lijunying
 * @date 2020/7/15 11:01
 */
public class TestMain {

//    给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？
//
//    示例:
//
//    输入: 3
//    输出: 5
//    解释:
//    给定 n = 3, 一共有 5 种不同结构的二叉搜索树:
//
//            1         3     3      2      1
//            \       /     /      / \      \
//            3     2     1      1   3      2
//            /     /       \                 \
//            2     1         2                 3

    public static void main(String[] args) {
//        for(int i=0;i<10;i++){
//            System.out.println(new TestMain().numTrees(i));
//        }
        System.out.println(new TestMain().numTrees(5));
    }

    public int numTrees(int n) {
        if(n<=0){
            return 0;
        }
        int[] array=new int[n+1];
        array[0]=1;
        for(int i=1;i<=n;i++){
            int half=i/2;
            int sum=0;
            if(i%2==1){
                sum=array[half]*array[half];
            }else{
                half--;
            }
            for(int j=half+1;j<i;j++){
                sum+=array[j]*array[i-j-1]*2;
            }
            array[i]=sum;
        }
        return array[n];
    }
}
